//给定一个二叉树，判断其是否是一个有效的二叉搜索树。 
//
// 假设一个二叉搜索树具有如下特征： 
//
// 
// 节点的左子树只包含小于当前节点的数。 
// 节点的右子树只包含大于当前节点的数。 
// 所有左子树和右子树自身必须也是二叉搜索树。 
// 
//
// 示例 1: 
//
// 输入:
//    2
//   / \
//  1   3
//输出: true
// 
//
// 示例 2: 
//
// 输入:
//    5
//   / \
//  1   4
//     / \
//    3   6
//输出: false
//解释: 输入为: [5,1,4,null,null,3,6]。
//     根节点的值为 5 ，但是其右子节点值为 4 。
// 
// Related Topics 树 深度优先搜索 递归 
// 👍 985 👎 0

package com.everyday.algorithm.changyf.leetcode.editor.cn;
public class ValidateBinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new ValidateBinarySearchTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {

    // 第一种方法：中序遍历一定是有序的
    // 第二种：一个节点的左树的最大值一定小于当前节点的值（VLmax > Vcur）
    //节点的右树的最小值一定大于当前节点的值（Vcur < VRmin）
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return process(root).isBST;
    }

    class Info {
        boolean isBST;
        int max;
        int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    Info process(TreeNode cur) {
        if (cur == null) {
            return null;
        }

        Info leftInfo = process(cur.left);
        Info rightInfo = process(cur.right);

        int max = cur.val;
        int min = cur.val;
        boolean isBST = true;

        if (leftInfo != null) {
            isBST = leftInfo.isBST && (leftInfo.max < cur.val);
            min = leftInfo.min;
        }

        if (rightInfo != null) {
            isBST = isBST && rightInfo.isBST && (rightInfo.min > cur.val);
            max = rightInfo.max;
        }


        return new Info(isBST, max, min);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}